package com.回溯法寻找矩阵中的路径;

public class Solution {
	public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
		boolean[] visited = new boolean[matrix.length];
		//这个数组是用来确定某个点是否已经被选取过
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				if (findpath(matrix, rows, cols, i, j, 0, str, visited)) {
					return true;
				}
			}
		}
		return false;

	}

	public boolean findpath(char[] matrix, int rows, int cols, int r, int c, int index, char[] str, boolean[] visited) {
		if (r < 0 || r >= rows || c < 0 || c >= cols || matrix[r * cols + c] != str[index] || visited[r * cols + c])
			return false;
		visited[r * cols + c] = true;
		if (index == str.length - 1)
			return true;
		if (findpath(matrix, rows, cols, r + 1, c, index + 1, str, visited)
				|| findpath(matrix, rows, cols, r - 1, c, index + 1, str, visited)
				|| findpath(matrix, rows, cols, r, c + 1, index + 1, str, visited)
				|| findpath(matrix, rows, cols, r, c - 1, index + 1, str, visited))
			return true;
		// 如果在这个点的上下左右都没有找到合适的点的时候,那么就要回到上一个节点去
		// 并且一定要将这个点重新改成false;
		//代表这个点没有被选取过
		visited[r * cols + c] = false;
		return false;
		

	}
}
